package com.jdaw.algorithm.kruskal;

import java.util.Arrays;

public class KruskalAlgorithm {
    private int edgeNum;//边的个数
    private char[] vertexs;
    private int[][] matrix;
    private static final int INF=Integer.MAX_VALUE;//表示两个顶点不连通

    public static void main(String[] args) {
        char[] vertexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        int matrix[][] = {
            /*A*//*B*//*C*//*D*//*E*//*F*//*G*/
    /*A*/ {   0,  12, INF, INF, INF,  16,  14},
    /*B*/ {  12,   0,  10, INF, INF,   7, INF},
    /*C*/ { INF,  10,   0,   3,   5,   6, INF},
    /*D*/ { INF, INF,   3,   0,   4, INF, INF},
    /*E*/ { INF, INF,   5,   4,   0,   2,   8},
    /*F*/ {  16,   7,   6, INF,   2,   0,   9},
    /*G*/ {  14, INF, INF, INF,   8,   9,   0}};
        KruskalAlgorithm kruskalAlgorithm=new KruskalAlgorithm(vertexs,matrix);
        kruskalAlgorithm.kruskal();
    }

    public KruskalAlgorithm(char[] vertexs, int[][] matrix) {
        int vlen=vertexs.length;
        this.vertexs = new char[vlen];
        for(int i=0;i<vertexs.length;i++){
            this.vertexs[i]=vertexs[i];
        }
        this.matrix = new int[vlen][vlen];
        for(int i=0;i<vertexs.length;i++){
            for(int j=0;j<vertexs.length;j++){
                this.matrix[i][j]=matrix[i][j];
            }
        }
        //统计共有几条边
        for(int i=0;i<vertexs.length;i++){
            for(int j=i+1;j<vertexs.length;j++){
                if(matrix[i][j]!=INF){
                    edgeNum++;
                }
            }
        }
    }

    public void kruskal(){
        int index=0;
        int[] ends=new int[edgeNum];//保存已有最小生成树中的每个顶点在最小生成树中的终点
        //结果数组
        EData[] rets=new EData[edgeNum];
        //获取图中所有边的集合，共有12条边
        EData[] edges=getEdges();
        //排序
        sortEdges(edges);
        //将边添加最小生成树中，判断是否生成回路
        for(int i=0;i<edgeNum;i++){
            int p1=getPosition(edges[i].start);
            int p2=getPosition(edges[i].end);
            int m=getEnd(ends,p1);
            int n=getEnd(ends,p2);
            if(m!=n){
                //若没有构成回路,要更新ends数组
                ends[m]=n;
                rets[index++]=edges[i];
            }
        }

        System.out.println("最小生成树为");
        for(int i = 0; i < index; i++) {
            System.out.println(rets[i]);
        }
    }

    //打印邻接矩阵
    public void printMatrix(){
        for(int i=0;i<matrix.length;i++){
            for(int j=0;j<matrix[0].length;j++){
                System.out.printf("%12d",matrix[i][j]);
            }
            System.out.println();
        }
    }

    //先对每条边的weight进行排序
    private void sortEdges(EData[] eDatas){
        for(int i=0;i<eDatas.length-1;i++){
            for (int j=0;j<eDatas.length-1-i;j++){
                if(eDatas[j].weight>eDatas[j+1].weight){
                    EData temp=eDatas[j];
                    eDatas[j]=eDatas[j+1];
                    eDatas[j+1]=temp;
                }
            }
        }
    }

    //返回顶点对应的下标
    private int getPosition(char ch){
        for(int i=0;i<vertexs.length;i++){
            if(vertexs[i]==ch){
                return i;
            }
        }
        return -1;
    }

    //获取图中的所有边
    private EData[] getEdges(){
        int index=0;
        EData[] edges=new EData[edgeNum];
        for(int i=0;i<vertexs.length;i++){
            for(int j=i+1;j<vertexs.length;j++){
                if(matrix[i][j]!=INF){
                    edges[index++]=new EData(vertexs[i],vertexs[j],matrix[i][j]);
                }
            }
        }
        return edges;
    }

    //获取下标为i的顶点的终点,ends数组记录了各个顶点的终点，在遍历过程中会逐渐加入
    public int getEnd(int[] ends,int i){
        while(ends[i]!=0){
            i=ends[i];
        }
        return i;
    }
}

//表示一条边对象
class EData{
    char start;
    char end;
    int weight;

    public EData(char start, char end, int weight) {
        this.start = start;
        this.end = end;
        this.weight = weight;
    }

    @Override
    public String toString() {
        return "EData [<" + start + ", " + end + ">= " + weight + "]";
    }
}
